package top;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author chenyw
 * @date 2022/7/11 22:06
 * @description     回溯加动态规划
 *      dp数组用来存储那些对应的下标是回文，避免重复计算，判断是否为回文子串的复杂度变为0
 *      dfs负责切分字符串
 */
public class Top131partition {
    List<List<String >> res = new ArrayList<>();
    List<String> list = new ArrayList<>();
    int n;
    boolean[][] dp;
    public List<List<String>> partition(String s) {
        n = s.length();
        dp = new boolean[n][n];
        //边界1 初始化对角线
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        //边界2 初始化对角线右上侧的斜线，表示相邻的两个字符是否为回文
        for (int i = 0; i < n - 1; i++) {
            dp[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
        }

        //便捷处理完毕转移方程开始：从下往上，从第三行开始补全右上三角
        //因为相邻的两个已经处理完毕，所以从第三个开始
        for (int i = n - 3; i >= 0 ; i--) {
            //从间隔为2(中间间隔2个)开始
            for (int j = i + 2; j < n; j++) {
                dp[i][j] = dp[i + 1][j - 1] && (s.charAt(i) == s.charAt(j));
            }
        }
        //开始递归进行分割字符串
        dfs(s, 0);
        return res;

    }
    //TODO dfs不清晰
    //负责分割字符串
    private void dfs(String s, int i) {
        if (i == n) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int j = i; j < n; j++) {
            if (dp[i][j]) {
                list.add(s.substring(i, j + 1));
                dfs(s, j + 1);
                list.remove(list.size() - 1);
            }
        }
    }
}
